package dp;

/**
 * 不同的二叉搜索树总数
 */
public class DifferentBinarySearchTree {

    public static void main(String[] args) {
        int n = 3;
        int result = getDifferentBSTCount(n);
        System.out.println(result);
    }

    private static int getDifferentBSTCount(int n) {
        int[] dp = new int[n+1];
        dp[0] = dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            // dp[i] = 以i到1的元素为头节点的二叉搜索树的种数
            // 通过计算左子树的种数和右子树的种数来得到以 i 为根节点的二叉搜索树的种数。左子树的节点范围是 1 ... (i-1)，右子树的节点范围是 (i+1) ... n。
            for (int j = 1; j <= i ; j++) {
                // 将j为根节点的数量左子树乘以右子树数量累加
                dp[i]+= dp[j-1]*dp[i-j];
            }
        }
        Common.print1dArr(dp);
        return dp[n];
    }
}
